package Demo5;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class CompleteBinaryTree {
    private int[] elems;
    private int usedSize;

    public CompleteBinaryTree() {
       this.elems = new int[10];//默认容量
    }

//    使用数组填充完全二叉树
    public void initCompleteBinaryTree(int[] array){
        for (int i = 0; i < array.length; i++) {
            this.elems[i] = array[i];
            usedSize++;
        }
    }

//    非递归前序遍历完全二叉树
    public List<Integer> preorderTraversal() {
        List<Integer> ret = new ArrayList<>();
        if (usedSize == 0){
            return ret;
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        while(!stack.isEmpty()){
            int cur = stack.pop();
            ret.add(elems[cur]);// 将当前节点的值添加到列表中

//            因为栈是后进先出 所以先让右子树进栈
            int rightChildIndex = 2 * cur + 2;
            int leftChildIndex = 2 * cur + 1;

            if (rightChildIndex < usedSize){
                stack.push(rightChildIndex);
            }
            if (leftChildIndex < usedSize){
                stack.push(leftChildIndex);
            }
        }
        return ret;
    }

}
